import tool.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import tool.TreeNodePrint;
import tool.input;

/**
 * @Description: levelOrder
 * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。
 * （即逐层地，从左到右访问所有节点）。
 * @Date:Create in 16:44  2022/7/19
 */
public class levelOrder0102 {
    public static void main(String[] args) {
        String s = "[3,9,20,null,null,15,7]";
        TreeNode root = input.getTree(s);
        TreeNodePrint.printTree(root);
        List<List<Integer>> resList = levelOrder1(root);
        System.out.println(resList.toString());
    }

    //BFS--迭代方式--借助队列
    public static List<List<Integer>> levelOrder1(TreeNode root) {

        List<List<Integer>> resList = new ArrayList<List<Integer>>();
        if(root==null) return resList;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);

        while(!que.isEmpty()){
            List<Integer> itemList = new ArrayList<>();
            int len = que.size();
            while(len>0){
                TreeNode temNode = que.poll();
                itemList.add(temNode.val);

                if(temNode.left!=null) que.offer(temNode.left);
                if(temNode.right!=null) que.offer(temNode.right);
                len--;
            }
            resList.add(itemList);
        }
        return resList;
    }

    //DFS--递归方式

}
